Introduction

• Modular arithmetic is a way of doing mathematics where numbers “wrap around’’ after reaching a certain value.
• The number $m$ is called the modulus.
• Saying two numbers are congruent mod $m$ means they leave the same remainder when divided by $m$.
• This article explains:
  • What congruence means
  • How to add, subtract, and multiply in modular arithmetic
  • Why these operations make sense
  • Common mistakes to avoid
  • Practical uses

The Meaning of Congruence mod $m$

• We write $$a \equiv b \pmod{m}$$ and read it as “$a$ is congruent to $b$ modulo $m$.”
• This means:
  • $a$ and $b$ have the same remainder when divided by $m$, or
  • $m$ divides the difference $a - b$.
• Examples:
  • $17 \equiv 5 \pmod{12}$ because both leave remainder $5$ when divided by $12$.
  • $-3 \equiv 4 \pmod{7}$ because $-3$ and $4$ differ by $7$.

Equivalence Classes and Remainders

• Every integer belongs to a “family’’ of numbers that are all congruent to each other mod $m$.
• These families are called equivalence classes.
• For modulus $m$, there are exactly $m$ classes:
  • The class of numbers congruent to $0$
  • The class of numbers congruent to $1$
  • …
  • The class of numbers congruent to $m-1$
• Each class can be represented by its remainder.
• Example for $m = 5$:
  • Class $[0]$: $\{\dots, -10, -5, 0, 5, 10, \dots\}$
  • Class $[1]$: $\{\dots, -9, -4, 1, 6, 11, \dots\}$

Well‑Defined Operations on Congruence Classes

• When we add or multiply congruence classes, we want the result to be independent of which representative we choose.
• Example:
  • If $7 \equiv 2 \pmod{5}$
  • and $12 \equiv 2 \pmod{5}$
  • then $7 + 12$ should be congruent to $2 + 2$ mod $5$.
• A mathematical operation is well‑defined if:
  • Choosing different representatives from the same class never changes the final congruence class.
• Addition and multiplication are well‑defined mod $m$.
• Division is not always well‑defined (more on this later).

Addition mod $m$

• To add numbers mod $m$:
  1. Add them normally.
  2. Reduce the result by taking the remainder mod $m$.
• Example:
  • Compute $9 + 14 \pmod{10}$
    • $9 + 14 = 23$
    • $23 \equiv 3 \pmod{10}$
• Properties:
  • Commutative: $a + b \equiv b + a$
  • Associative: $(a + b) + c \equiv a + (b + c)$
  • Identity element: $0$
  • Every number has an additive inverse (its negative mod $m$)

Multiplication mod $m$

• Multiply as usual, then reduce mod $m$.
• Example:
  • Compute $7 \cdot 8 \pmod{10}$
    • $7 \cdot 8 = 56$
    • $56 \equiv 6 \pmod{10}$
• Properties:
  • Commutative
  • Associative
  • Distributive over addition
• Multiplicative identity: $1$
• Not every number has a multiplicative inverse mod $m$ (depends on gcd).

Subtraction and Negatives mod $m$

• Subtraction is just addition of a negative: $$a - b \equiv a + (-b) \pmod{m}$$
• To find $-b$ mod $m$:
  • Compute $m - b$ (if $b \neq 0$)
• Example:
  • $3 - 10 \pmod{7}$
    • $3 + (-10)$
    • $-7 \equiv 0 \pmod{7}$

Exponentiation mod $m$

• Repeated multiplication, reducing at each step.
• Example:
  • Compute $3^4 \pmod{5}$
    • $3^2 = 9 \equiv 4$
    • $3^4 = (3^2)^2 \equiv 4^2 = 16 \equiv 1$
• Useful facts:
  • Exponentiation grows fast, so reducing early keeps numbers small.
  • Patterns often repeat (important in cryptography).

Division mod $m$

Division in modular arithmetic is more subtle than addition, subtraction, or multiplication. It only works when the number you want to divide by has a multiplicative inverse modulo $m$.

What does division mean mod $m$?

• In ordinary arithmetic, dividing by $b$ means multiplying by $1/b$.
• In modular arithmetic, dividing by $b$ means multiplying by a number $b^{-1}$ such that $$b \cdot b^{-1} \equiv 1 \pmod{m}.$$
• This number $b^{-1}$ is called the multiplicative inverse of $b$ mod $m$.

When does an inverse exist?

• A number $b$ has an inverse mod $m$ if and only if $$\gcd(b, m) = 1.$$
• In other words:
  • If $b$ and $m$ share no common factors (other than $1$), division is possible.
  • If they share a factor, division is not well‑defined.

Examples

• Example 1: $3^{-1} \pmod{7}$
  • Modulus $m = 7$
  • $3$ and $7$ are coprime
  • $3$ has an inverse mod $7$
  • In fact, $3 \cdot 5 = 15 \equiv 1 \pmod{7}$, so $3^{-1} \equiv 5$.
• Example 2: $4^{-1} \pmod{10}$
  • Modulus $m = 10$
  • $4$ and $10$ share a factor of $2$
  • $4$ has no inverse mod $10$
  • So expressions like $a/4 \pmod{10}$ do not make sense.

How to compute an inverse (conceptually)

For beginners, it’s enough to know:

• Try small numbers until you find one that works.
• Use the fact that the inverse must satisfy $$b \cdot x \equiv 1 \pmod{m}.$$

Example: Find the inverse of $7$ mod $12$

• Try small $x$:
  • $7 \cdot 7 = 49 \equiv 1 \pmod{12}$
• So $7^{-1} \equiv 7$.

Advanced readers can solve the linear diophantine equation: $$ax + my = 1$$

Using division once the inverse is known

To compute $$\frac{a}{b} \pmod{m},$$ rewrite it as $$a \cdot b^{-1} \pmod{m}.$$ Example: Compute $6 / 3 \pmod{7}$

• First find $3^{-1} \equiv 5$
• Then compute $6 \cdot 5 = 30 \equiv 2 \pmod{7}$
• So $6/3 \equiv 2$.

Key takeaways

• Division is not always allowed in modular arithmetic.
• It only works when the divisor has an inverse.
• Inverses exist exactly when the divisor and modulus are coprime.
• When an inverse exists, division becomes multiplication by that inverse.

When Operations Are (and Aren’t) Well‑Defined

• Addition: always well‑defined
• Multiplication: always well‑defined
• Exponentiation: well‑defined because it uses multiplication
• Division:
  • Not always allowed
  • $a/b \pmod{m}$ only makes sense if $b$ has a multiplicative inverse mod $m$
  • This happens exactly when $\gcd(b, m) = 1$

Working with Modular Identities

• Common identities:
  • If $a \equiv b$ and $c \equiv d$, then
    • $a + c \equiv b + d$
    • $a - c \equiv b - d$
    • $a c \equiv b d$
• Reducing early often simplifies calculations.
• Example:
  • Compute $27 \cdot 19 \pmod{8}$
    • $27 \equiv 3$
    • $19 \equiv 3$
    • $3 \cdot 3 = 9 \equiv 1$

Common Pitfalls and Misconceptions

• Mistake: Thinking $a \equiv b$ means $a = b$
  • They only match modulo $m$.
• Mistake: Forgetting to reduce after operations.
• Mistake: Trying to divide when no inverse exists.
• Mistake: Mixing up the modulus (e.g., switching between mod $7$ and mod $10$).

Applications of Modular Arithmetic

• Clocks: Hours wrap around after $12$ or $24$.
• Computer science:
  • Hashing
  • Checksums
  • Random number generators
• Cryptography:
  • RSA uses exponentiation mod a large number.
• Number theory:
  • Studying patterns in primes
  • Solving Diophantine equations

Exercises

1. Compute $17 + 29 \pmod{12}$.

   Solution

   Compute $17 + 29 \pmod{12}$

   • Step 1: $17 + 29 = 46$
   • Step 2: Divide $46$ by $12$:
     • $12 \cdot 3 = 36$, remainder $10$
   • Answer: $$17 + 29 \equiv 10 \pmod{12}$$
2. Compute $45 - 62 \pmod{9}$.

   Solution

   Compute $45 - 62 \pmod{9}$

   • Step 1: $45 - 62 = -17$
   • Step 2: Reduce $-17$ mod $9$:
     • Add $9$ twice: $-17 + 18 = 1$
   • Answer: $$45 - 62 \equiv 1 \pmod{9}$$
3. Compute $8 \cdot 14 \pmod{11}$.

   Solution

   Compute $8 \cdot 14 \pmod{11}$

   • Step 1: $8 \cdot 14 = 112$
   • Step 2: Reduce $112$ mod $11$:
     • $11 \cdot 10 = 110$, remainder $2$
   • Answer: $$8 \cdot 14 \equiv 2 \pmod{11}$$
4. Compute $3^5 \pmod{7}$.

   Solution

   Compute $3^5 \pmod{7}$

   • Step 1: $3^2 = 9 \equiv 2 \pmod{7}$
   • Step 2: $3^4 = (3^2)^2 \equiv 2^2 = 4 \pmod{7}$
   • Step 3: $3^5 = 3^4 \cdot 3 \equiv 4 \cdot 3 = 12 \equiv 5 \pmod{7}$
   • Answer: $$3^5 \equiv 5 \pmod{7}$$
5. Determine whether $37 \equiv -8 \pmod{5}$.

   Solution

   Determine whether $37 \equiv -8 \pmod{5}$

   • Step 1: Reduce $37$ mod $5$:
     • $37 = 5 \cdot 7 + 2$, so $37 \equiv 2 \pmod{5}$
   • Step 2: Reduce $-8$ mod $5$:
     • $-8 + 10 = 2$, so $-8 \equiv 2 \pmod{5}$
   • Conclusion: Both are congruent to $2$ mod $5$.
   • Answer: $$37 \equiv -8 \pmod{5}$$
6. Reduce each number mod $6$:
   • $19$
   • $-4$
   • $28$

   Solution

   Reduce each number mod $6$: $19$, $-4$, $28$

   • $19 \pmod{6}$:
     • $6 \cdot 3 = 18$, remainder $1$
     • $19 \equiv 1 \pmod{6}$
   • $-4 \pmod{6}$:
     • $-4 + 6 = 2$
     • $-4 \equiv 2 \pmod{6}$
   • $28 \pmod{6}$:
     • $6 \cdot 4 = 24$, remainder $4$
     • $28 \equiv 4 \pmod{6}$
   • Answer: $$19 \equiv 1,\quad -4 \equiv 2,\quad 28 \equiv 4 \pmod{6}$$
7. Compute $27 \cdot 19 \pmod{8}$ using early reduction.

   Solution

   Compute $27 \cdot 19 \pmod{8}$ using early reduction

   • Step 1: Reduce first:
     • $27 \equiv 3 \pmod{8}$ (since $27 - 24 = 3$)
     • $19 \equiv 3 \pmod{8}$ (since $19 - 16 = 3$)
   • Step 2: Multiply reduced numbers:
     • $3 \cdot 3 = 9$
   • Step 3: Reduce $9$ mod $8$:
     • $9 \equiv 1 \pmod{8}$
   • Answer: $$27 \cdot 19 \equiv 1 \pmod{8}$$
8. Find the additive inverse of $5$ mod $13$.

   Solution

   Find the additive inverse of $5$ mod $13$

   • Goal: Find $x$ such that $$5 + x \equiv 0 \pmod{13}$$
   • Step 1: Think of $-5$ mod $13$:
     • $-5 + 13 = 8$
   • Check: $5 + 8 = 13 \equiv 0 \pmod{13}$
   • Answer:
     The additive inverse of $5$ mod $13$ is $8$.
9. Division: Does $4$ have a multiplicative inverse mod $10$?
   • If yes, find it.
   • If no, explain why division by $4$ is not possible.

   Solution

   Division: Does $4$ have a multiplicative inverse mod $10$?

   • Check gcd:
     • $\gcd(4, 10) = 2 \neq 1$
   • Conclusion:
     • Since $4$ and $10$ are not coprime, $4$ has no inverse mod $10$.
     • Therefore, division by $4$ is not well‑defined mod $10$.
   • Answer:
     $4$ does not have a multiplicative inverse mod $10$.
10. Division: Compute $6 / 3 \pmod{7}$ by finding the inverse of $3$.

    Solution

    Division: Compute $6 / 3 \pmod{7}$ by finding the inverse of $3$

    • Step 1: Find $3^{-1} \pmod{7}$:
      • Try small numbers:
        • $3 \cdot 1 = 3 \not\equiv 1$
        • $3 \cdot 2 = 6 \not\equiv 1$
        • $3 \cdot 3 = 9 \equiv 2$
        • $3 \cdot 4 = 12 \equiv 5$
        • $3 \cdot 5 = 15 \equiv 1 \pmod{7}$
      • So $3^{-1} \equiv 5 \pmod{7}$.
    • Step 2: Rewrite division as multiplication: $$\frac{6}{3} \equiv 6 \cdot 3^{-1} \equiv 6 \cdot 5 \pmod{7}$$
    • Step 3: Compute $6 \cdot 5 = 30 \equiv 2 \pmod{7}$
    • Answer: $$6 / 3 \equiv 2 \pmod{7}$$
11. Compute $123 + 456 + 789 \pmod{9}$.

    Solution

    Compute $123 + 456 + 789 \pmod{9}$

    You can either add first or use the digit‑sum trick for mod $9$.

    • Method 1: Direct sum
      • $123 + 456 = 579$
      • $579 + 789 = 1368$
      • Reduce $1368$ mod $9$:
        • Sum of digits: $1 + 3 + 6 + 8 = 18$
        • $18 \equiv 0 \pmod{9}$
    • Method 2: Reduce each term mod $9$
      • $123 \equiv 1 + 2 + 3 = 6 \pmod{9}$
      • $456 \equiv 4 + 5 + 6 = 15 \equiv 6 \pmod{9}$
      • $789 \equiv 7 + 8 + 9 = 24 \equiv 6 \pmod{9}$
      • Total: $6 + 6 + 6 = 18 \equiv 0 \pmod{9}$
    • Answer: $$123 + 456 + 789 \equiv 0 \pmod{9}$$